#include <iostream>
#include "contextchain.h"
#include "slots.h"
size_t kswitchCounter = 0;
/*
 * @brief 每执行一次relin增加一次密钥交换次数
 *
 */
void LogRelin()
{
    ++kswitchCounter;
}
/*
 * @brief 每执行一次galois增加一次密钥交换次数
 *
 */
void LogGalois()
{
    ++kswitchCounter;
}

poly SlotRing::SubringView::Generator()
{
    poly result = { 0, 1 };
    PolyReduceMod(result, scalarMod, polyMod);
    return result;
}
/*
 * @brief 计算给定数 x 在模 mod2N 下的阶
 * @param x 要计算阶的数。
 * @param mod2N 模数 2N，必须为正整数且不为 0。
 * @return 返回 x 在模 mod2N 下的阶 k。如果找不到合适的阶，返回 0。
 */
size_t OrderMod2N(uint64_t x, const uint64_t &mod2N)
{
    if (mod2N == 0) {
        cout << "模数为0" << endl;
    }
    uint64_t current = x % mod2N;
    for (int i = 0; i < Log2Exact(mod2N); ++i) {
        if (current == 1) {
            return static_cast<uint64_t>(1) << i;
        } else {
            current = MultiplyUintMod(current, current, mod2N);
        }
    }
    return 0;
}
/*
 * @brief 判断数 x 是否属于由生成元 gen 生成的子群
 * @param x 要检查的数。
 * @param gen 子群的生成元。
 * @param order 子群的阶，即生成元的最大幂。
 * @param mod2N 模数 2N，必须为正整数且不为 0。
 * @return 如果 x 是由 gen 生成的子群的元素，返回 `true`；否则返回 `false`。
 */
bool IsInSubgroup(uint64_t x, uint64_t gen, size_t order, const uint64_t &mod2N)
{
    uint64_t current = 1;
    uint64_t mulGen;
    if (mod2N == 0) {
        cout << "模数为0" << endl;
    }
    mulGen = gen % mod2N;
    for (size_t i = 0; i < order; ++i) {
        if (current == x) {
            return true;
        }
        current = MultiplyUintMod(current, mulGen, mod2N);
    }
    return false;
}
/*
 * @brief 判断一个群是否是循环群
 * 给定一个生成元 `gen` 和群的阶 `order`，通过计算 `gen^(order / 2)` 的结果，
 * 并判断它是否属于由生成元 `p` 生成的子群。如果不属于，则认为该群是循环群。
 * @param gen 群的生成元。
 * @param order 群的阶。
 * @param ordP 子群 `p` 的阶。
 * @param p 子群的生成元。
 * @param mod2N 模数 2N，必须为正整数且不为 0。
 * @return 如果群是循环群，返回 `true`；否则返回 `false`。
 */
bool IsGroupCyclic(uint64_t gen, size_t order, size_t ordP, uint64_t p, const uint64_t &mod2N)
{
    uint64_t genPowNHalf = ModExp(gen, order / 2, mod2N);
    return !IsInSubgroup(genPowNHalf, p, ordP, mod2N);
}
/*
 * @brief 初始化环群
 */
void SlotRing::InitSlotGroup()
{
    d = OrderMod2N(p, mod2N);
    if (d == 0) {
        cout << "模数为0" << endl;
    }
    n = N() / d;
    slotGroupCyclic = IsGroupCyclic(g1, n, d, p, mod2N);
}

void SlotRing::InitPLog()
{
    uint64_t mul_g1;
    mul_g1 = g1;
    uint64_t current = 1;
    for (size_t i = 0; i < 2; ++i) {
        for (size_t j = 0; j < N() / 2; ++j) {
            if (current == p % mod2N) {
                pLog = std::make_tuple(j, i);
                return;
            }
            current = MultiplyUintMod(current, mul_g1, mod2N);
        }
        current = MultiplyUintMod(current, g2, mod2N);
    }
    assert(false);
}
/*
 * @brief 初始化槽模数以及自同构生成对应系数
 *
 * @param baseUnitVector 初始的槽系数矩阵
 */
void SlotRing::InitSlotModulus(poly baseUnitVector)
{
    assert(baseUnitVector.size() == N());
    if (slotGroupCyclic) {
        poly current = baseUnitVector;
        for (size_t i = 0; i < n; ++i) {
            unitVectors.push_back(current);
            G1Automorphism(current, 1);
        }
    } else {
        poly current = baseUnitVector;
        for (size_t i = 0; i < n / 2; ++i) {
            unitVectors.push_back(current);
            G1Automorphism(current, 1);
        }
        current = baseUnitVector;
        G2Automorphism(current);
        for (size_t i = 0; i < n / 2; ++i) {
            unitVectors.push_back(current);
            G1Automorphism(current, 1);
        }
    }
    poly f;
    f.resize(N() + 1);
    f[0] = 1;
    f[N()] = 1;

    poly a = std::move(baseUnitVector);
    a[0] = SubUintMod(a[0], 1, modPe);
    poly factor = std::get<2>(PolyEea(a, f, modPe));
    assert(factor[d] != 0);
    uint64_t lc_inv = InvMod_(factor[d], modPe);
    PolyScale(factor, NegateUintMod(lc_inv, modPe), modPe);
    assert(factor[d] == NegateUintMod(1, modPe));
    factor[d] = 0;
    PolyNormalize(factor);
    assert(IsPolySparse(factor, d / 2));
    slotModulus.n = d;
    slotModulus.xPowerN = std::move(factor);
}
/*
 * @brief 对多项式执行 G1 自同构变换
 *
 * 该函数对输入的多项式执行基于 G1 生成元的自同构变换。自同构变换通过系数的交换和取反来实现。
 * 函数会处理循环群中的元素，并根据需要应用第二生成元。
 *
 * @param x 要进行自同构变换的多项式，作为引用传入并原地修改
 * @param iters 自同构变换的迭代次数，表示应用 G1 自同构的次数
 * @param mod 可选的模数指针，如果为 nullptr 则使用默认的 modPe
 */
void SlotRing::G1Automorphism(poly &x, size_t iters, const uint64_t *mod) const
{
    if (iters == 0) {
        return;
    }
    if (mod == nullptr) {
        mod = &modPe;
    }
    iters = iters % G1Ord();

    unsigned long logPower2Iters = HighestDividingPower2(iters);
    uint64_t power2Iters = static_cast<uint64_t>(1) << logPower2Iters;
    uint64_t oddIters = iters / power2Iters;

    uint64_t gMul;
    gMul = ModExp(g1, oddIters, mod2N);
    uint64_t stepMul;
    stepMul = ModExp(g1, iters, mod2N);

    const auto swapEntries = [&](uint64_t fst, uint64_t snd) {
        bool fstRed = fst >= N();
        bool sndRed = snd >= N();
        if (fstRed) {
            fst -= N();
        }
        if (sndRed) {
            snd -= N();
        }
        std::swap(x[fst], x[snd]);
        if (fstRed != sndRed) {
            if (fst != snd) {
                x[fst] = NegateUintMod(x[fst], *mod);
                x[snd] = NegateUintMod(x[snd], *mod);
            } else {
                x[fst] = NegateUintMod(x[fst], *mod);
            }
        }
    };

    for (size_t i = 0; i <= log2N - 2; ++i) {
        uint64_t base = static_cast<uint64_t>(1) << i;
        // the log of number of entries until the sequence (base * (g1^iters)^i) % N starts repeating
        int64_t logStepOrder;
        bool hasSecondGenerator;
        // this strange logic here is because (Z/2Z)* and (Z/4Z)* are cyclic, but afterwards not anymore
        if (log2N <= i + 3) {
            logStepOrder = log2N - 2 - i - logPower2Iters;
            hasSecondGenerator = false;
        } else {
            logStepOrder = log2N - 3 - i - logPower2Iters;
            hasSecondGenerator = true;
        }

        if (logStepOrder <= 0) {
            // in this case, have that X -> +/- X
            for (size_t k = 0; k < power2Iters; ++k) {
                if ((MultiplyUintMod(base, stepMul, mod2N) >= N()) != (base >= N())) {
                    x[base % N()] = NegateUintMod(x[base % N()], *mod);
                }
                if (hasSecondGenerator) {
                    base = MultiplyUintMod(base, g2, mod2N);
                    if ((MultiplyUintMod(base, stepMul, mod2N) >= N()) != (base >= N())) {
                        x[base % N()] = NegateUintMod(x[base % N()], *mod);
                    }
                }
                base = MultiplyUintMod(base, gMul, mod2N);
            }
        } else {
            for (size_t k = 0; k < power2Iters; ++k) {
                // otherwise, we cycle through the sequence (base * (g1^iters)^i) % N
                // and swap/negate coefficients
                uint64_t current = base;
                for (size_t j = 0; j < (static_cast<uint64_t>(1) << logStepOrder); ++j) {
                    current = MultiplyUintMod(current, stepMul, mod2N);
                    swapEntries(base, current);
                }
                if (hasSecondGenerator) {
                    base = MultiplyUintMod(base, g2, mod2N);
                    current = base;
                    for (size_t j = 0; j < (static_cast<uint64_t>(1) << logStepOrder); ++j) {
                        current = MultiplyUintMod(current, stepMul, mod2N);
                        swapEntries(base, current);
                    }
                }
                base = MultiplyUintMod(base, gMul, mod2N);
            }
        }
    }
}
/*
 * @brief 对多项式执行 G2 自同构变换
 *
 * 该函数对输入的多项式执行基于 G2 生成元的自同构变换。G2 生成元在 (Z/2NZ)* 中的阶为 2。
 * 自同构变换通过系数的交换和取反来实现。
 *
 * @param x 要进行自同构变换的多项式，作为引用传入并原地修改
 * @param mod 可选的模数指针，如果为 nullptr 则使用默认的 modPe
 */
void SlotRing::G2Automorphism(poly &x, const uint64_t *mod) const
{
    if (mod == nullptr) {
        mod = &modPe;
    }
    // we heavily use that g2 has order 2 in (Z/2NZ)*
    uint64_t partner = 0;
    for (uint64_t base = 0; base < N(); ++base) {
        if (partner >= N() && partner - N() == base) {
            x[base] = NegateUintMod(x[base], *mod);
        } else if (partner >= N() && base < (partner - N())) {
            std::swap(x[base], x[partner - N()]);
            x[base] = NegateUintMod(x[base], *mod);
            x[partner - N()] = NegateUintMod(x[partner - N()], *mod);
        } else if (partner < N() && base < partner) {
            std::swap(x[base], x[partner]);
        }
        partner = AddUintMod(partner, g2, mod2N);
    }
}
/*
 * @brief 对多项式应用 Frobenius 自同构变换
 *
 * 该函数实现了 Frobenius 自同构变换，通过组合 G1 和 G2 自同构来完成。
 * Frobenius 自同构是一种特殊的自同构变换，在有限域上将元素映射到其 p 次方。
 *
 * @param x 要进行 Frobenius 变换的多项式，作为引用传入并原地修改
 * @param iters Frobenius 变换的迭代次数，表示应用 p^iters 次方运算
 * @param mod 可选的模数指针，如果为 nullptr 则使用默认的 modPe
 */
void SlotRing::ApplyFrobenius(poly &x, size_t iters, const uint64_t *mod) const
{
    G1Automorphism(x, (iters * std::get<0>(pLog)) % G1Ord(), mod);
    if ((iters * std::get<1>(pLog)) % 2 != 0) {
        G2Automorphism(x);
    }
}

SlotRing::SlotRing(uint64_t log2N, uint64_t p, uint64_t e, uint64_t g2, poly baseUnitVector)
    : log2N(log2N),
      p(p),
      e(e),
      modPe(Exponentiate(p, e)),
      mod2N(static_cast<uint64_t>(1) << log2N),
      g1(3),
      g2(g2),
      mod2NCyclotomic()
{
    mod2NCyclotomic.n = N();
    mod2NCyclotomic.xPowerN = { NegateUintMod(1, modPe) };
    InitSlotGroup();
    assert(OrderMod2N(g1, mod2N) == N() / 2);
    assert(OrderMod2N(g2, mod2N) == 2);
    dSparse = IsPolySparse(baseUnitVector, d);

    // assert that <g1, g2> is the whole index group
    assert(!IsInSubgroup(g2, g1, N() / 2, mod2N));
    InitPLog();

    // currently, we assume that baseUnitVector is a polynomial in X^(d/2)
    assert(IsPolySparse(baseUnitVector, d / 2));
    InitSlotModulus(std::move(baseUnitVector));
}

SlotRing::SlotRing(uint64_t log2N, uint64_t p, uint64_t e, poly baseUnitVector)
    : SlotRing(log2N, p, e, (static_cast<uint64_t>(1) << (log2N - 1)) - 1, baseUnitVector)
{}

/*
 * @brief 自举明文的128位解码
 * @param x 需要解码的多项式
 * @param slot 需要解码的多项式的槽下标
 * @return result 解码后对应下标的多项式
 */
poly SlotRing::ExtractSlotValue(poly x, size_t slot) const
{
    if (slotGroupCyclic) {
        const size_t shift = slot % n;
        G1Automorphism(x, G1Ord() - shift);
    } else {
        const size_t g1Shift = slot % (n / 2);
        const size_t g2Shift = (slot / (n / 2)) % 2;
        G1Automorphism(x, G1Ord() - g1Shift);
        if (g2Shift != 0) {
            G2Automorphism(x);
        }
    }
    PolyReduceMod(x, modPe, slotModulus);
    return x;
}
/*
 * @brief 自举明文的128位编码
 * @param x 需要编码到对应槽的多项式
 * @param slot 需要编码到多项式的槽的下标
 * @return result 编码后的的多项式
 */
poly SlotRing::FromSlotValue(const poly &x, size_t slot) const
{
    poly result = PolyMulMod(x, unitVectors[0], modPe, mod2NCyclotomic);
    if (slotGroupCyclic) {
        const size_t shift = slot % n;
        G1Automorphism(result, shift);
    } else {
        const size_t g1Shift = slot % (n / 2);
        const size_t g2Shift = (slot / (n / 2)) % 2;
        G1Automorphism(result, g1Shift);
        if (g2Shift != 0) {
            G2Automorphism(result);
        }
    }
    return result;
}

const poly &SlotRing::SlotOne(size_t slot) const noexcept
{
    return unitVectors[slot % n];
}

uint64_t SlotRing::N() const noexcept
{
    return static_cast<uint64_t>(1) << (log2N - 1);
}

bool SlotRing::IsPolySparse(const poly &xPowerN, size_t dPoly)
{
    if (dPoly <= 1) {
        return true;
    }
    for (size_t i = 0; i < xPowerN.size(); ++i) {
        if (dPoly == 0) {
            cout << " d为0 " << endl;
        }
        if ((xPowerN[i] != 0) && (i % dPoly != 0)) {
            return false;
        }
    }
    return true;
}

bool SlotRing::IsDHalfSparse() const
{
    // we assume that this is always the case, and check it in the constructor via check_poly_sparse()
    return true;
}

bool SlotRing::IsDSparse() const
{
    return dSparse;
}
/*
 * @brief 构造环的幂次子环
 *
 * 该函数通过提取原环中的特定元素构造一个新的幂次子环。新子环的维度会相应减小。
 *
 * @param indexLog2 子环的指数对数,用于确定子环的大小
 * @return SlotRing 返回构造的幂次子环
 */
SlotRing SlotRing::PowerXSubring(size_t indexLog2) const
{
    const size_t index = static_cast<uint64_t>(1) << indexLog2;
    assert(IsDHalfSparse());
    assert((static_cast<uint64_t>(1) << indexLog2) <= d);
    poly newBaseUnitVector;
    newBaseUnitVector.resize(unitVectors[0].size() / index);
    for (size_t i = 0; i < unitVectors[0].size(); ++i) {
        if (i % index == 0) {
            newBaseUnitVector[i / index] = unitVectors[0][i];
        } else {
            // this should already be guaranteed, but check anyway
            assert(unitVectors[0][i] == 0);
        }
    }
    uint64_t newIndexModulus = static_cast<uint64_t>(1) << (log2N - indexLog2);
    SlotRing result(log2N - indexLog2, p, e, g2 % newIndexModulus, std::move(newBaseUnitVector));

    poly check1;
    poly tmp = unitVectors[0];
    G2Automorphism(tmp);
    InPowerXSubring(result, tmp, check1);
    poly check2 = result.unitVectors[0];
    result.G2Automorphism(check2);
    assert(check1 == check2);

    return result;
}
/*
 * @brief 将主环中的多项式映射到子环中
 * 该函数执行以下操作:
 * 1. 验证主环的大小是子环大小的整数倍
 * 2. 清空并调整结果多项式的大小
 * 3. 仅保留原多项式中索引为 index 整数倍的系数
 * 4. 如果原多项式在其他位置有非零系数，则抛出异常*
 * @param subring 目标子环
 * @param el 要映射的多项式
 * @param result 映射结果将存储在此多项式中
 *
 */
void SlotRing::InPowerXSubring(const SlotRing &subring, const poly &el, poly &result) const
{
    assert(N() % subring.N() == 0);
    const size_t index = N() / subring.N();
    result.clear();
    result.resize(el.size() / index);
    for (size_t i = 0; i < el.size(); ++i) {
        if (i % index == 0) {
            result[i / index] = el[i];
        } else if (el[i] != 0) {
            throw std::invalid_argument("Given polynomial is not contained in the subring");
        }
    }
}
/*
 * @brief 将子环中的多项式映射到主环中
 *
 * 该函数执行以下操作:
 * 1. 验证主环的大小是子环大小的整数倍
 * 2. 清空并调整结果多项式的大小
 * 3. 将源多项式的每个系数映射到目标多项式中，间隔为 index
 *
 * @param subring 源子环
 * @param el 要映射的多项式
 * @param result 映射结果将存储在此多项式中
 *
 */
void SlotRing::FromPowerXSubring(const SlotRing &subring, const poly &el, poly &result) const
{
    assert(N() % subring.N() == 0);
    const size_t index = N() / subring.N();
    result.clear();
    result.resize(el.size() * index);
    for (size_t i = 0; i < el.size(); ++i) {
        result[i * index] = el[i];
    }
}

SlotRing SlotRing::ChangeExponent(uint64_t newExp) const
{
    assert(newExp > 0);
    assert(newExp <= e);
    uint64_t modNew(Exponentiate(p, newExp));
    poly newBaseUnitVector;
    for (uint64_t x : unitVectors[0]) {
        newBaseUnitVector.push_back(x % modNew);
    }
    SlotRing result(log2N, p, newExp, std::move(newBaseUnitVector));
    assert(result.d == d);
    assert(result.n == n);
    assert(result.pLog == pLog);
    return result;
}
/*
 * @brief 执行分块旋转操作
 *
 * 该函数创建一个用于分块旋转的 Rotation 对象。分块旋转允许在固定大小的块内进行循环移位，
 * 而不是在整个多项式上进行。
 * 函数的主要步骤:
 * 1. 验证 blockSize 的有效性
 * 2. 计算有效块大小(考虑非循环群的特殊情况)
 * 3. 构造前向掩码(forwardMask):
 * - 对每个块，保留不会被移出块的元素
 * 4. 构造后向掩码(backwardMask):
 * - 对每个块，保留会被移出块的元素
 * 5. 创建并返回 Rotation 对象*
 * @param slots 要旋转的位置数量
 * @param blockSize 每个块的大小
 * @return SlotRing::Rotation 返回一个可以执行指定旋转的 Rotation 对象
 */
SlotRing::Rotation SlotRing::BlockRotate(size_t slots, size_t blockSize) const
{
    if (blockSize == 0) {
        cout << " blockSize为0 " << endl;
    }
    assert(SlotGroupLen() % blockSize == 0);
    poly forwardMask;

    // due to the order in which we store the unit vectors, this is also fine if !slotGroupCyclic
    size_t effectiveBlockSize = blockSize;
    if (!slotGroupCyclic && blockSize == n) {
        effectiveBlockSize = n / 2;
    }
    const size_t effectiveBlockCount = SlotGroupLen() / effectiveBlockSize;
    const size_t s = slots % effectiveBlockSize;

    for (size_t i = 0; i < effectiveBlockCount; ++i) {
        for (size_t j = 0; j < effectiveBlockSize - s; ++j) {
            PolyAdd(forwardMask, unitVectors[i * effectiveBlockSize + j], modPe);
        }
    }
    poly backwardMask;
    for (size_t i = 0; i < effectiveBlockCount; ++i) {
        for (size_t j = effectiveBlockSize - s; j < effectiveBlockSize; ++j) {
            PolyAdd(backwardMask, unitVectors[i * effectiveBlockSize + j], modPe);
        }
    }
    Rotation result(std::move(forwardMask), std::move(backwardMask), slots % blockSize, *this, blockSize);
    assert(result.EffectiveBlockSize() == effectiveBlockSize);
    return result;
}
/*
 * @brief 多项式长度为512的环测试参数，p=127，value为对应的系数映射数组
 *
 * @return std::shared_ptr<SlotRing>
 */
std::shared_ptr<SlotRing> SmallTestParameters()
{
    poly unitVector;
    unitVector.resize(512);
    auto values = { 1,  124, 4,   120, 11, 109, 29,  80,  76, 4,   72,  59, 13, 46, 94,  79, 15, 64,  78,  113, 92,  21,
        71, 77,  121, 83,  38, 45,  120, 52,  68, 111, 84,  27, 57, 97, 87,  10, 77, 60,  17,  43,  101, 69,
        32, 37,  122, 42,  80, 89,  118, 98,  20, 78,  69,  9,  60, 76, 111, 92, 19, 73,  73,  0,   73,  54,
        19, 35,  111, 51,  60, 118, 69,  49,  20, 29,  118, 38, 80, 85, 122, 90, 32, 58,  101, 84,  17,  67,
        77, 117, 87,  30,  57, 100, 84,  16,  68, 75,  120, 82, 38, 44, 121, 50, 71, 106, 92,  14,  78,  63,
        15, 48,  94,  81,  13, 68,  72,  123, 76, 47,  29,  18, 11, 7,  4,   3,  1,  2 };
    auto it = values.end();
    for (size_t i = 0; i < 128; ++i) {
        --it;
        unitVector[4 * i] = *it;
    }
    return std::make_shared<SlotRing>(10, 127, 1, std::move(unitVector));
}
/*
 * @brief 多项式长度为512的环测试参数，p=257，value为对应的系数映射数组
 *
 * @return std::shared_ptr<SlotRing>
 */
std::shared_ptr<SlotRing> SmallP257TestParameters()
{
    poly unitVector;
    unitVector.resize(512);
    auto values = { 142, 59,  77,  70,  87,  9,   125, 137, 218, 58,  6,   169, 177, 231, 210, 4,   27,  118, 154,
        140, 174, 18,  250, 17,  179, 116, 12,  81,  97,  205, 163, 8,   54,  236, 51,  23,  91,  36,
        243, 34,  101, 232, 24,  162, 194, 153, 69,  16,  108, 215, 102, 46,  182, 72,  229, 68,  202,
        207, 48,  67,  131, 49,  138, 32,  216, 173, 204, 92,  107, 144, 201, 136, 147, 157, 96,  134,
        5,   98,  19,  64,  175, 89,  151, 184, 214, 31,  145, 15,  37,  57,  192, 11,  10,  196, 38,
        128, 93,  178, 45,  111, 171, 62,  33,  30,  74,  114, 127, 22,  20,  135, 76,  256, 186, 99,
        90,  222, 85,  124, 66,  60,  148, 228, 254, 44,  40,  13,  152, 255 };
    auto it = values.end();
    for (size_t i = 0; i < 128; ++i) {
        --it;
        unitVector[4 * i] = *it;
    }
    return std::make_shared<SlotRing>(10, 257, 1, std::move(unitVector));
}
/*
 * @brief 多项式长度为32768的环测试参数，p=127，coefficients为对应的系数映射数组
 * @return std::shared_ptr<SlotRing>
 */
std::shared_ptr<SlotRing> P127TestParameters()
{
    auto coefficients = { 1993024, 240875,  1207593, 404466,  20647,   348018,  811998,  401243,  1072206, 620779,
        953549,  755478,  795511,  145718,  598024,  1753912, 1101795, 1868445, 1456233, 2048122,
        1712610, 1283514, 1465554, 1560331, 67929,   1866101, 1288626, 1400697, 1138076, 534561,
        784782,  480838,  1522444, 840918,  927040,  291915,  532443,  394526,  680455,  1554433,
        1544666, 593498,  1618356, 1931381, 1791404, 1865968, 788282,  822881,  1782322, 190115,
        1837873, 1709323, 1712134, 1718364, 451719,  239328,  644360,  1208324, 278256,  1940492,
        1672965, 2046996, 1599175, 1599175, 1387,    1672965, 107891,  278256,  840059,  644360,
        1809055, 451719,  330019,  1712134, 339060,  1837873, 1858268, 1782322, 1225502, 788282,
        182415,  1791404, 117002,  1618356, 1454885, 1544666, 493950,  680455,  1653857, 532443,
        1756468, 927040,  1207465, 1522444, 1567545, 784782,  1513822, 1138076, 647686,  1288626,
        182282,  67929,   488052,  1465554, 764869,  1712610, 261,     1456233, 179938,  1101795,
        294471,  598024,  1902665, 795511,  1292905, 953549,  1427604, 1072206, 1647140, 811998,
        1700365, 20647,   1643917, 1207593, 1807508, 1993024, 32006 };
    auto indices = { 32512, 32256, 32000, 31744, 31488, 31232, 30976, 30720, 30464, 30208, 29952, 29696, 29440,
        29184, 28928, 28672, 28416, 28160, 27904, 27648, 27392, 27136, 26880, 26624, 26368, 26112,
        25856, 25600, 25344, 25088, 24832, 24576, 24320, 24064, 23808, 23552, 23296, 23040, 22784,
        22528, 22272, 22016, 21760, 21504, 21248, 20992, 20736, 20480, 20224, 19968, 19712, 19456,
        19200, 18944, 18688, 18432, 18176, 17920, 17664, 17408, 17152, 16896, 16640, 16128, 15872,
        15616, 15360, 15104, 14848, 14592, 14336, 14080, 13824, 13568, 13312, 13056, 12800, 12544,
        12288, 12032, 11776, 11520, 11264, 11008, 10752, 10496, 10240, 9984,  9728,  9472,  9216,
        8960,  8704,  8448,  8192,  7936,  7680,  7424,  7168,  6912,  6656,  6400,  6144,  5888,
        5632,  5376,  5120,  4864,  4608,  4352,  4096,  3840,  3584,  3328,  3072,  2816,  2560,
        2304,  2048,  1792,  1536,  1280,  1024,  768,   512,   256,   0 };
    poly unitVector;
    unitVector.resize(1 << 15);
    auto indexIt = indices.begin();
    auto coeffIt = coefficients.begin();
    for (; indexIt != indices.end(); ++indexIt, ++coeffIt) {
        unitVector[*indexIt] = *coeffIt;
    }
    return std::make_shared<SlotRing>(16, 127, 3, std::move(unitVector));
}
/*
 * @brief 多项式长度为32768的环测试参数，p=257，coefficients为对应的系数映射数组
 * @return std::shared_ptr<SlotRing>
 */
std::shared_ptr<SlotRing> P257TestParameters()
{
    std::initializer_list<uint64_t> coefficients = {
        7964572,  6261607,  16240935, 102099,   8906165,  9188787,  6652056,  6514830,  13560566, 4058859,  6803824,
        2637246,  14964259, 8700452,  13885406, 12517446, 3289884,  7193548,  14438928, 14310157, 5483269,  14464749,
        7681466,  12493558, 15081196, 16410594, 12121931, 2032437,  14600010, 10166868, 4700179,  13476574, 983850,
        9275880,  13267162, 16806538, 13190359, 11592792, 7816384,  14932248, 13347910, 5088061,  14931724, 5704791,
        15187352, 16367455, 12927940, 16583969, 13166475, 2450967,  2314130,  14807101, 16693874, 3439246,  7937160,
        8764025,  7597636,  1868854,  15532357, 13962877, 1688878,  11856744, 13426589, 3975308,  8638757,  11867405,
        4139446,  1645406,  2719681,  14214557, 15278080, 7294824,  6060464,  13542772, 10988902, 14604673, 12583496,
        6989727,  13949465, 555184,   3553200,  14152308, 1356854,  588714,   6387435,  961982,   8029853,  7134849,
        1050653,  14661907, 15973513, 16635621, 6987326,  13622481, 9026649,  3426195,  6011323,  13036503, 10929998,
        396662,   3442686,  15482513, 13212403, 8408813,  11334031, 8307382,  3360145,  2311480,  6280586,  7839149,
        11153619, 11748240, 11615815, 3330562,  14514936, 8478652,  16688123, 8347227,  3293264,  6218689,  2032504,
        16192770, 1262895,  15951777, 3579793,  7381310,  2299274,  16841979
    };
    auto indices = { 32512, 32256, 32000, 31744, 31488, 31232, 30976, 30720, 30464, 30208, 29952, 29696, 29440,
        29184, 28928, 28672, 28416, 28160, 27904, 27648, 27392, 27136, 26880, 26624, 26368, 26112,
        25856, 25600, 25344, 25088, 24832, 24576, 24320, 24064, 23808, 23552, 23296, 23040, 22784,
        22528, 22272, 22016, 21760, 21504, 21248, 20992, 20736, 20480, 20224, 19968, 19712, 19456,
        19200, 18944, 18688, 18432, 18176, 17920, 17664, 17408, 17152, 16896, 16640, 16384, 16128,
        15872, 15616, 15360, 15104, 14848, 14592, 14336, 14080, 13824, 13568, 13312, 13056, 12800,
        12544, 12288, 12032, 11776, 11520, 11264, 11008, 10752, 10496, 10240, 9984,  9728,  9472,
        9216,  8960,  8704,  8448,  8192,  7936,  7680,  7424,  7168,  6912,  6656,  6400,  6144,
        5888,  5632,  5376,  5120,  4864,  4608,  4352,  4096,  3840,  3584,  3328,  3072,  2816,
        2560,  2304,  2048,  1792,  1536,  1280,  1024,  768,   512,   256,   0 };
    poly unitVector;
    unitVector.resize(1 << 15);
    auto indexIt = indices.begin();
    auto coeffIt = coefficients.begin();
    for (; indexIt != indices.end(); ++indexIt, ++coeffIt) {
        unitVector[*indexIt] = *coeffIt;
    }
    return std::make_shared<SlotRing>(SlotRing(16, 257, 3, std::move(unitVector)).ChangeExponent(2));
}
/*
 * @brief 自同构测试函数
 *
 */
void TestGAutomorphisms()
{
    SlotRing r = *SmallTestParameters();
    assert(r.SlotGroupDims() == 1);
    assert(r.SlotGroupLen() == 64);
    assert(r.SlotRank() == 8);

    poly p;
    p.resize(512);
    p[1] = 1;
    r.G1Automorphism(p, 1);
    poly expected;
    expected.resize(512);
    expected[3] = 1;
    assert(expected == p);

    p.clear();
    p.resize(512);
    expected.clear();
    expected.resize(512);
    p[0] = 2;
    p[3] = 1;
    p[256] = 1;
    p[257] = 4;
    expected[0] = 2;
    expected[9] = 1;
    expected[256] = 126;
    expected[259] = 123;
    r.G1Automorphism(p, 1);
    assert(expected == p);

    p.clear();
    p.resize(512);
    expected.clear();
    expected.resize(512);
    p[1] = 1;
    p[2] = 2;
    p[3] = 4;
    p[5] = 8;   // this is not in the group <g1>
    p[11] = 16; // this is in the group <g1>, but not in <g1^2>
    p[25] = 32; // this is in the group <g1^2>, but not in <g1^4>
    expected[497] = 126;
    expected[482] = 125;
    expected[467] = 123;
    expected[437] = 119;
    expected[347] = 111;
    expected[137] = 95;
    r.G1Automorphism(p, 3 * 4);
    assert(expected == p);

    std::cout << "TestGAutomorphisms(): success" << std::endl;
}
/*
 * @brief 循环旋转测试函数
 *
 */
void TestBlockRotate()
{
    SlotRing slotRing = *SmallTestParameters();
    Context context(9, { 1099511590913 }, { 1099511592961 }, slotRing.R().scalarMod, 3.2);

    SlotRing::Rotation rot = slotRing.BlockRotate(3, 32);

    KeyGenerator keygen(&context);
    std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
    SecretKey sk(*tmp.first);
    PublicKey pk(*tmp.second);
    vector<uint64_t> galoisVector;
    galoisVector = { std::get<0>(rot.GaloisElements()), std::get<1>(rot.GaloisElements()) };
    GaloisKeys gk(*keygen.GenGaloisKeys(galoisVector, &sk));

    PkEncryptor encryptor(&context, &pk);
    Evaluator evaluator(&context);
    Decryptor decryptor(&context, &sk);

    poly a = slotRing.FromSlotValue({ 1, 1 }, 0);
    PolyAdd(a, slotRing.FromSlotValue({ 2, 0, 3 }, 1), slotRing.R().scalarMod);
    PolyAdd(a, slotRing.FromSlotValue({ 4, 0, 1 }, 16), slotRing.R().scalarMod);
    PolyAdd(a, slotRing.FromSlotValue({ 0, 1 }, 17), slotRing.R().scalarMod);
    Plaintext xPlain({ a }, context.MaxLevel());

    evaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);

    Ciphertext xEnc(&context, 1, context.MaxLevel());
    encryptor.Encrypt(&xPlain, &xEnc);

    Ciphertext resultEnc(&context, 1, context.MaxLevel());
    rot.ApplyCiphertext(xEnc, evaluator, gk, resultEnc);

    Plaintext result(&context, 0);
    decryptor.Decrypt(&resultEnc, &result);
    evaluator.lightEncoder->ScaleDown(&result, &result);

    poly resultPoly(&result.value->Coeffs[0][0], &result.value->Coeffs[0][0] + slotRing.N());
    poly expected;
    PolyAdd(expected, slotRing.FromSlotValue({ 1, 1 }, 3), slotRing.R().scalarMod);
    PolyAdd(expected, slotRing.FromSlotValue({ 2, 0, 3 }, 4), slotRing.R().scalarMod);
    PolyAdd(expected, slotRing.FromSlotValue({ 4, 0, 1 }, 19), slotRing.R().scalarMod);
    PolyAdd(expected, slotRing.FromSlotValue({ 0, 1 }, 20), slotRing.R().scalarMod);

    assert(rot(a) == expected);
    assert(resultPoly == expected);

    std::cout << "TestBlockRotate(): success" << std::endl;
}
/*
 * @brief 非循环旋转测试函数
 *
 */
void TestRotateNoncyclic()
{
    SlotRing base = *P257TestParameters();
    SlotRing slotRing = base.ChangeExponent(2);
    int logN = log2(slotRing.N());
    Context context(logN, { 1099506515969, 1099507695617 }, { 1099510054913 }, slotRing.R().scalarMod, 3.2);

    KeyGenerator keygen(&context);
    std::pair<SecretKey *, PublicKey *> tmp = keygen.GenKeyPair();
    SecretKey sk(*tmp.first);
    PublicKey pk(*tmp.second);
    PkEncryptor encryptor(&context, &pk);
    Evaluator evaluator(&context);
    Decryptor decryptor(&context, &sk);

    poly a = slotRing.FromSlotValue({ 1, 1 }, 0);
    PolyAdd(a, slotRing.FromSlotValue({ 2, 0, 3 }, 63), slotRing.R().scalarMod);
    PolyAdd(a, slotRing.FromSlotValue({ 0, 1 }, 65), slotRing.R().scalarMod);
    Plaintext xPlain(a, context.MaxLevel());
    evaluator.lightEncoder->ScaleUp(&xPlain, &xPlain);
    Ciphertext xEnc(&context, 1, context.MaxLevel());
    encryptor.Encrypt(&xPlain, &xEnc);
    {
        SlotRing::Rotation rot = slotRing.Rotate(3);

        vector<uint64_t> galoisVector;
        galoisVector = { std::get<0>(rot.GaloisElements()), std::get<1>(rot.GaloisElements()) };
        GaloisKeys gk(*keygen.GenGaloisKeys(galoisVector, &sk));

        Ciphertext resultEnc(&context, 1, context.MaxLevel());
        rot.ApplyCiphertext(xEnc, evaluator, gk, resultEnc);

        Plaintext result(&context, context.MaxLevel());
        decryptor.Decrypt(&resultEnc, &result);
        evaluator.lightEncoder->ScaleDown(&result, &result);

        poly resultPoly;
        resultPoly.resize(result.value->Coeffs[0].size());
        for (int i = 0; i < resultPoly.size(); i++) {
            resultPoly[i] = result.value->Coeffs[0][i];
        }
        resultPoly.resize(slotRing.N());
        poly expected;
        PolyAdd(expected, slotRing.FromSlotValue({ 1, 1 }, 3), slotRing.R().scalarMod);
        PolyAdd(expected, slotRing.FromSlotValue({ 2, 0, 3 }, 66), slotRing.R().scalarMod);
        PolyAdd(expected, slotRing.FromSlotValue({ 0, 1 }, 68), slotRing.R().scalarMod);
        assert(rot(a) == expected);
        assert(resultPoly == expected);
    }
    {
        SlotRing::Rotation rot = slotRing.Rotate(67);

        vector<uint64_t> galoisVector;
        galoisVector = { std::get<0>(rot.GaloisElements()), std::get<1>(rot.GaloisElements()) };
        GaloisKeys gk(*keygen.GenGaloisKeys(galoisVector, &sk));

        Ciphertext resultEnc(&context, 1, context.MaxLevel());
        rot.ApplyCiphertext(xEnc, evaluator, gk, resultEnc);

        Plaintext result(&context, context.MaxLevel());
        decryptor.Decrypt(&resultEnc, &result);
        evaluator.lightEncoder->ScaleDown(&result, &result);

        poly resultPoly;
        resultPoly.resize(result.value->Coeffs[0].size());
        for (int i = 0; i < resultPoly.size(); i++) {
            resultPoly[i] = result.value->Coeffs[0][i];
        }
        resultPoly.resize(slotRing.N());
        poly expected;
        PolyAdd(expected, slotRing.FromSlotValue({ 1, 1 }, 67), slotRing.R().scalarMod);
        PolyAdd(expected, slotRing.FromSlotValue({ 2, 0, 3 }, 2), slotRing.R().scalarMod);
        PolyAdd(expected, slotRing.FromSlotValue({ 0, 1 }, 4), slotRing.R().scalarMod);
        assert(rot(a) == expected);
        assert(resultPoly == expected);
    }
    std::cout << "TestRotateNoncyclic(): success" << std::endl;
}

size_t SlotRing::Rotation::EffectiveBlockSize() const
{
    if (blockSize == slotRing.n && !slotRing.slotGroupCyclic) {
        return slotRing.n / 2;
    } else {
        return blockSize;
    }
}

poly SlotRing::Rotation::operator () (const poly &x) const
{
    if (s == 0) {
        return x;
    }
    poly a = PolyMulMod(x, fMask, slotRing.modPe, slotRing.mod2NCyclotomic);
    poly b = PolyMulMod(x, bMask, slotRing.modPe, slotRing.mod2NCyclotomic);
    assert(b.size() == slotRing.N());
    slotRing.G1Automorphism(a, s % EffectiveBlockSize());
    slotRing.G1Automorphism(b, slotRing.G1Ord() + s % EffectiveBlockSize() - EffectiveBlockSize());
    if (blockSize == slotRing.n && !slotRing.slotGroupCyclic) {
        slotRing.G2Automorphism(b);
    }
    PolyAdd(a, b, slotRing.modPe);
    if (s >= EffectiveBlockSize()) {
        slotRing.G2Automorphism(a);
    }
    return a;
}
/*
 * @brief 对密文应用旋转操作
 *
 * 该函数对输入的密文执行旋转变换。旋转操作通过以下步骤实现:
 * 1. 如果旋转位数为0，直接返回输入密文
 * 2. 如果旋转位数等于有效块大小，执行单次Galois变换
 * 3. 否则执行完整的旋转操作:
 * - 使用前向掩码和后向掩码将输入分成两部分
 * - 对两部分分别应用不同的Galois变换
 * - 将变换后的结果相加得到最终结果
 *
 * @param in 输入密文
 * @param eval 评估器对象,用于执行同态运算
 * @param gk Galois密钥,用于执行自同构变换
 * @param result 存储旋转结果的密文
 * @throw std::invalid_argument 如果输入和输出引用相同
 */
void SlotRing::Rotation::ApplyCiphertext(Ciphertext &in, Evaluator &eval, GaloisKeys &gk, Ciphertext &result)
{
    if (&in == &result) {
        throw std::invalid_argument("This function does not accept the same reference for in and result.");
    }
    if (s == 0) {
        result = in;
        return;
    }
    if (s == EffectiveBlockSize()) {
        result = in;

        eval.ApplyGaloisInplace(&result, static_cast<uint32_t>(std::get<0>(GaloisElements())),
            gk.GetGaloisKey(static_cast<uint32_t>(std::get<0>(GaloisElements()))));
        return;
    }
    if (fMaskPlain == nullptr) {
        fMaskPlain = std::make_unique<Plaintext>(fMask, eval.params->MaxLevel());
        bMaskPlain = std::make_unique<Plaintext>(bMask, eval.params->MaxLevel());
    }
    Plaintext *fmas = fMaskPlain.get();
    Plaintext *bmas = bMaskPlain.get();

    Ciphertext backward(in.value[0]->Coeffs[0].size(), in.Degree(), in.Level());

    eval.Mul(&in, fmas, &result, MultiType::plaintextRingT);
    eval.Mul(&in, bmas, &backward, MultiType::plaintextRingT);

    eval.ApplyGaloisInplace(&result, static_cast<uint32_t>(std::get<0>(GaloisElements())),
        gk.GetGaloisKey(static_cast<uint32_t>(std::get<0>(GaloisElements()))));
    LogGalois();
    eval.ApplyGaloisInplace(&backward, static_cast<uint32_t>(std::get<1>(GaloisElements())),
        gk.GetGaloisKey(static_cast<uint32_t>(std::get<1>(GaloisElements()))));
    LogGalois();
    eval.Add(&result, &backward, &result);
}
/*
 * @brief 获取前向旋转的G1和G2分解
 *
 * 该函数计算前向旋转操作所需的G1和G2生成元的幂次。根据块大小和群的循环性质，
 * 返回不同的分解结果。
 *
 * @details 函数的处理逻辑:
 * 1. 如果块大小等于n且群非循环:
 * - 当旋转位数s大于等于有效块大小时，返回(s % EffectiveBlockSize, 1)
 * - 否则返回(s % EffectiveBlockSize, 0)
 * 2. 其他情况下返回(s % EffectiveBlockSize, 0)
 *
 * @return 返回一个元组，包含:
 * - 第一个元素: G1生成元的幂次(对有效块大小取模)
 * - 第二个元素: G2生成元的幂次(0或1)
 */
const std::tuple<uint64_t, uint64_t> SlotRing::Rotation::GetForwardG1G2Decomp() const
{
    if (blockSize == slotRing.n && !slotRing.slotGroupCyclic) {
        if (s >= EffectiveBlockSize()) {
            return std::make_tuple(s % EffectiveBlockSize(), 1);
        } else {
            return std::make_tuple(s % EffectiveBlockSize(), 0);
        }
    } else {
        return std::make_tuple(s % EffectiveBlockSize(), 0);
    }
}
/*
 * @brief 获取后向旋转的G1和G2分解
 *
 * 该函数计算后向旋转操作所需的G1和G2生成元的幂次。根据块大小和群的循环性质，
 * 返回不同的分解结果。
 * 函数的处理逻辑:
 * 1. 如果块大小等于n且群非循环:
 * - 当旋转位数s大于等于有效块大小时，返回(G1Ord + s % EffectiveBlockSize - EffectiveBlockSize, 0)
 * - 否则返回(G1Ord + s % EffectiveBlockSize - EffectiveBlockSize, 1)
 * 2. 其他情况下返回(G1Ord + s - EffectiveBlockSize, 0)
 * @return 返回一个元组，包含:
 * - 第一个元素: G1生成元的幂次
 * - 第二个元素: G2生成元的幂次(0或1)
 */
const std::tuple<uint64_t, uint64_t> SlotRing::Rotation::GetBackwardG1G2Decomp() const
{
    if (blockSize == slotRing.n && !slotRing.slotGroupCyclic) {
        if (s >= EffectiveBlockSize()) {
            return std::make_tuple(slotRing.G1Ord() + s % EffectiveBlockSize() - EffectiveBlockSize(), 0);
        } else {
            return std::make_tuple(slotRing.G1Ord() + s % EffectiveBlockSize() - EffectiveBlockSize(), 1);
        }
    } else {
        return std::make_tuple(slotRing.G1Ord() + s - EffectiveBlockSize(), 0);
    }
}
/*
 * @brief 生成自同构需要的galois元素
 *
 */
std::tuple<uint32_t, uint32_t> SlotRing::Rotation::GaloisElements() const
{
    std::tuple<uint64_t, uint64_t> forward_g1_g2 = GetForwardG1G2Decomp();
    std::tuple<uint64_t, uint64_t> backward_g1_g2 = GetBackwardG1G2Decomp();
    return std::make_tuple(
        static_cast<uint32_t>(MultiplyUintMod(ModExp(slotRing.g1, std::get<0>(forward_g1_g2), slotRing.IndexMod()),
        ModExp(slotRing.g2, std::get<1>(forward_g1_g2), slotRing.IndexMod()), slotRing.IndexMod())),
        static_cast<uint32_t>(MultiplyUintMod(ModExp(slotRing.g1, std::get<0>(backward_g1_g2), slotRing.IndexMod()),
        ModExp(slotRing.g2, std::get<1>(backward_g1_g2), slotRing.IndexMod()), slotRing.IndexMod())));
}

poly SlotRing::Frobenius::operator () (poly x) const
{
    if (iters == 0) {
        return x;
    }
    assert(x.size() <= slotRing.N());
    x.resize(slotRing.N());
    slotRing.ApplyFrobenius(x, iters);
    return x;
}

const std::tuple<uint64_t, uint64_t> SlotRing::Frobenius::GetG1G2Decomp() const
{
    return std::make_tuple(MultiplyUintMod(std::get<0>(slotRing.pLog), iters, slotRing.IndexMod()),
        MultiplyUintMod(std::get<1>(slotRing.pLog), iters, slotRing.IndexMod()));
}
/*
 * @brief 生成自同构需要的galois元素
 *
 */
uint32_t SlotRing::Frobenius::galois_element() const
{
    std::tuple<uint64_t, uint64_t> g1_g2_decomp = GetG1G2Decomp();
    return static_cast<uint32_t>(MultiplyUintMod(ModExp(slotRing.g1, std::get<0>(g1_g2_decomp), slotRing.IndexMod()),
        ModExp(slotRing.g2, std::get<1>(g1_g2_decomp), slotRing.IndexMod()), slotRing.IndexMod()));
}

poly SlotRing::RawAuto::operator () (poly x) const
{
    assert(x.size() <= slotRing.N());
    x.resize(slotRing.N());
    slotRing.G1Automorphism(x, std::get<0>(g1g2Decomp));
    if (std::get<1>(g1g2Decomp) % 2 != 0) {
        slotRing.G2Automorphism(x);
    }
    return x;
}
/*
 * @brief 对密文进行galois自同构
 *
 * @param in 输入的密文
 * @param eval 计算器，包含自同构函数
 * @param gk galois密钥，可提取对应galois变换的秘钥
 * @param result 自同构的结果存储在result中
 */
void SlotRing::RawAuto::ApplyCiphertext(Ciphertext &in, Evaluator &eval, GaloisKeys &gk, Ciphertext &result)
{
    if (g1g2Decomp == std::make_tuple(0, 0)) {
        result = in;
        return;
    }
    eval.ApplyGalois(&in, static_cast<uint32_t>(galois_element()),
        gk.GetGaloisKey(static_cast<uint32_t>(galois_element())), &result);
    LogGalois();
}

uint32_t SlotRing::RawAuto::galois_element() const
{
    uint64_t result = ModExp(slotRing.g1, std::get<0>(g1g2Decomp), slotRing.IndexMod());
    if (std::get<1>(g1g2Decomp) % 2 != 0) {
        result = MultiplyUintMod(result, slotRing.g2, slotRing.IndexMod());
    }
    return static_cast<uint32_t>(result);
}

bool SlotRing::RawAuto::is_identity() const
{
    return galois_element() == 1;
}